1. Technical Field
The present invention relates generally to routing protocol technology and, more particularly, to a method and system for providing bio-inspired routing protocols using overhearing and/or probabilistic path finding in a mobile ad hoc network.
2. Description of the Related Art
Existing mobile ad hoc routing protocols based on proactive/reactive methods periodically or a periodically generate a large number of control packets, thus incurring routing overhead and a delay in path finding. Also, in an existing routing algorithm, because the best path is selected in such a way that, intermediate nodes autonomously determine the nodes subsequent thereto, it is difficult to guarantee the end-to-end quality of service (QoS) performance required for actual transmission service.
Furthermore, in the case of multi-path routing protocols, load balancing problems may arise from the decreased overall capacity of networks, the exhaustion of resources of a specific terminal, or the like. In comparison with the existing mobile ad hoc routing algorithm, a bio-inspired routing algorithm has the following characteristics.
First, because ants, bees and the like can search for an optimized path in a dynamically changing environment in a dispersed and independent manner, a routing algorithm that takes inspiration from this is appropriate for autonomously maintaining optimal network status without administrative intervention in spite of various changes in the mobile network environment.
Second, in colonies of organisms, although the multiple entities have limited resources, they easily search for the best path using flexible adaptability. Therefore, when only limited resources are available in a large-scale network, it may be applied in order to reduce overhead and maximize routing performance.
Finally, because the bio-inspired, routing algorithm adapts to various changes in the external situation and thereby solves problems by itself, it is possible to quickly recover from unpredictable path failure and/or loss, which may occur during movement. Accordingly, bio-inspired routing protocols are being proposed.
A representative example of such a bio-inspired routing protocol is AntHocNet. AntHocNet has two features of ad hoc routing protocols, namely, reactive routing and proactive routing. First, when there is no information about a route to the destination, the process of setting up a route is performed based on reactive routing. Also, when link failure occurs, a local route repair process is performed and warning messages are sent based on the reactive routing. Meanwhile, a route maintenance process for maintaining and improving existing route information is performed based on proactive routing.
The AntHocNet basically follows a routing method based on distance vectors, but pheromones, acquired by processing the distance vectors in a probabilistic manner, may be used in place of the distance vectors. The use of pheromones is the main characteristic of the ant-based bio-inspired routing protocol. AntHocNet uses two kinds of pheromone information, that is, regular pheromones and virtual pheromones, and a routing table separately stores the two kinds of pheromones. The regular pheromone is defined as the inverse number of the cost of reaching a destination node, and may thus serve as a measure of the ‘goodness’ of the corresponding path.
Meanwhile, the virtual pheromone corresponds to another kind of information for estimating the goodness of a path, and may be acquired through calculation based on the goodness reported from neighboring nodes during a proactive route maintenance process.
The AntHocNet starts a reactive route setup process when a routing table contains no information about the destination to which data packets created in a source are to be delivered. To this end, a reactive forward ant packet is broadcast over a network. However, if an intermediate node that receives this packet has routing information about the corresponding destination, the intermediate node forwards the packet by unicast. In this case, the intermediate node determines the next node n to which the packet is to be sent in a probabilistic manner using the following Equation (1):
                                          P            in            d                    =                                                    (                                  τ                  in                  d                                )                                            β                1                                                                    ∑                                  j                  ∈                                      N                    t                    d                                                              ⁢                                                (                                      τ                    ij                    d                                    )                                                  β                  1                                                                    ,                              β            1                    ≥          1                                    (        1        )            where Pind denotes the probability of selecting the next node n in the path from the node i to the destination d, τind denotes the regular pheromone value for the path from the node i to the destination d via the next node n, Nid denotes the set of neighboring nodes that may provide the path from the node i to the destination d, and β1 denotes a weighted constant for controlling the probability value. As shown in Equation (1), the probability value is determined in proportion to the regular pheromone value τind.
Conversely, if the intermediate node has no routing information about the corresponding destination, the intermediate node forwards the packet by broadcast. Here, in order to reduce flooding overhead, each node forwards only the first arrived packet, among the arrived reactive forward ant packets. The reactive forward ant packet is delivered while storing information about the nodes through which the reactive forward ant packet has passed en route to the destination. When the reactive forward ant packet reaches the destination, a reactive backward ant packet is created at the destination.
The reactive backward ant packet is created such that information about the path along which the reactive forward ant packet has traveled is copied into the header thereof, whereby the reactive backward ant packet is sent to the source by backtracking. In this process, information about the quality of each link in the path is collected, and based on the information about the quality, the intermediate nodes and the source node calculate the pheromone value for the destination and update their routing tables.
Also, after the first path is established, the AntHocNet starts a proactive route maintenance process. As a result, routing information is periodically updated and/or improved. The proactive route maintenance process includes two subprocesses, namely, pheromone diffusion and proactive ant sampling. First among these, pheromone diffusion serves to diffuse pheromone information, and is similar to a pheromone diffusion phenomenon in nature. To this end, all nodes on the network periodically broadcast their best pheromone information (which is the greatest value of the pheromone values for each destination in the routing table) regardless of the presence of a communication session. The best pheromone information is delivered using a Hello message, and all the nodes asynchronously deliver the message at a Hello interval. The neighboring node, having received the Hello message, updates its pheromone value by combining the known cost information with the received best pheromone information using the following Equation (2):κjid=((νid)−1+cjt)−1  (2)where νid denotes the best pheromone information for the best path from the node i to the destination d, and cjt denotes the locally maintained cost value and represents the cost of sending a packet from the no de j to the node i.
As shown in Equation (2), the value acquired by adding the cost value cjt to the inverse number of the best pheromone value νid, which is received from the neighboring node i, becomes the total cost value for the path from the node j to the destination d via the node i, and the inverse number thereof becomes a new pheromone value κjid. Each node diffuses the updated pheromone value at preset intervals. Here, the pheromone value acquired through the pheromone diffusion is called a virtual pheromone, and it is managed separately.
In comparison with the virtual pheromone, a pheromone acquired by path finding using ant packets is called a regular pheromone. The virtual pheromone is used only to support proactive ant sampling. In other words, the virtual pheromone is used only when a proactive forward ant packet is forwarded, and afterwards the regular pheromone is acquired through a proactive backward ant packet.
Proactive ant sampling is the process by which a proactive forward ant packet is created and path sampling is performed using the proactive forward ant packet, whereby the regular pheromone information is updated. To this end, all the source nodes periodically create proactive forward ant packets and send them to a destination while a communication session is maintained. Here, the transmission interval of the proactive forward ant packets is set to the Hello interval. The proactive forward ant packets are forwarded in a probabilistic manner, and the probability value for selecting the next hop is determined in consideration of both the regular pheromone and the virtual pheromone. The proactive forward ant packet selects the next node n using the probability value acquired using the following Equation (3):
                                          P                          i              ⁢                                                          ⁢              n                        d                    =                                                    [                                  max                  ⁡                                      (                                                                  τ                                                  i                          ⁢                                                                                                          ⁢                          n                                                d                                            ,                                              ω                                                  i                          ⁢                                                                                                          ⁢                          n                                                d                                                              )                                                  ]                                            β                2                                                                    ∑                                  j                  ∈                                      N                    j                    d                                                              ⁢                                                [                                      max                    ⁡                                          (                                                                        τ                          ij                          d                                                ,                                                  ω                          ij                          d                                                                    )                                                        ]                                                  β                  2                                                                    ,                              β            2                    ≥          1                                    (        3        )            where Pind, τind, and Nid are the same as the values defined above, ωind denotes the virtual pheromone value for the path from the node i to the destination d via the next node n, and β2 denotes a weighted constant for controlling the probability value. As shown in Equation (3), the greater value, among the regular pheromone τind and the virtual pheromone ωind, is used, and the probability value that is proportional to the greater value is calculated.
When the proactive forward ant packet reaches the destination, it is converted into a proactive backward ant packet and backtracks to the source node while leaving only a regular pheromone. In other words, the proactive ant packet tracks the virtual pheromone, but when it reaches the destination, the pheromone information is converted into the regular pheromone. Consequently, a new path is recommended through pheromone diffusion, and a proactive ant packet checks the new path.
Meanwhile, a data packet is forwarded by a hop-by-hop transmission method, in which the next node is determined based on a local pheromone value, in which case only a regular pheromone is used. When a data packet is transmitted, the probability of forwarding the packet to the next node n is calculated using the following Equation (4):
                                          P            nd                    =                                                    (                                  τ                                      i                    ⁢                                                                                  ⁢                    n                                    d                                )                                            β                3                                                                    ∑                                  j                  ∈                                      N                    i                    d                                                              ⁢                                                (                                      τ                    ij                    d                                    )                                                  β                  3                                                                    ,                              β            3                    ≥          1                                    (        4        )            where β3 denotes a weighted constant for controlling the probability value.
Meanwhile, pheromone diffusion and proactive ant sampling in the AntHocNet may cause significant overhead. Such overhead may be caused because all the nodes on the network must periodically send a Hello message which includes their best pheromone information, and must periodically transmit proactive ant packets in both directions. Here, the periodic transmission of control packets may increase overhead and thus decrease the efficiency of transmission of data packets.
Also, the pheromone diffusion process of the AntHocNet is based on Destination-Sequenced Distance Vector (DSDV) routing, but DSDV is known to have a low speed when tracking the change of topology in a high-mobility environment. That is, because the pheromone diffusion process of the AntHocNet may have decreased convergence speed in a high-mobility environment, it is disadvantageous in that correct routing information for a destination may not be provided.
Furthermore, in the proactive route maintenance process of the AntHocNet, a stagnation problem, in which the same path is repeatedly found because the process depends mainly on a regular pheromone value if there is no significant change in a virtual pheromone, may occur. The stagnation problem signifies the unnecessary creation of proactive ant packets, and may increase overhead. Also, it is highly probable that an alternative path to be used in the event of link failure cannot be secured in advance.